package leetcode100

// TODO 单调栈 [经典] 【-】 每日温度
// TODO https://leetcode.cn/problems/daily-temperatures/solution/mei-ri-wen-du-cong-bao-li-dao-dan-diao-z-fti3/

// 时间复杂度：O(N) N 是温度列表的长度
// 空间复杂度：O(N) N 是温度列表的长度
func dailyTemperatures(temperatures []int) []int {
	n := len(temperatures)
	res := make([]int, n)
	var stack []int // 栈，存储下标 声明为 nil
	//stack := make([]int, n) // 栈，存储下标 声明且初始化
	for i := 0; i < n; i++ {
		// 栈不为空 && 当前天温度大于栈顶天温度
		for len(stack) != 0 && temperatures[i] > temperatures[stack[len(stack)-1]] {
			// 栈顶元素
			prevIndex := stack[len(stack)-1]
			// 出栈
			stack = stack[:len(stack)-1]
			// 设置栈顶天的结果值
			res[prevIndex] = i - prevIndex
		}
		// 入栈
		stack = append(stack, i)
	}
	return res
}
